
/*
 * Question: Try to propose an nonrecursive algorithm
 * that traverse a binary tree in postorder.
 */

#include <iostream>
#include <stack>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char> 
{
};

struct snode {
	bitree *rt;
	int tag;
};

void visit(bitree *rt)
{
    cout << rt->key << " ";
}

void postorder(bitree *rt)
{
    snode n;
    stack<snode> s;
	bitree *p;

	p = rt;
	while (p || !s.empty()){
		if (p){
			n.rt = p; n.tag = 0;
			s.push(n);
			p = p->lchild;
		}
		else{
			n = s.top(); s.pop();
			p = n.rt;
			if (!n.tag){
				n.tag = 1; s.push(n);
				p = p->rchild;
			}
			else{
				cout << p->key << " ";
				p = NULL;
			}
		}
	}
} 

int main()
{
    bitree *rt;

    bitree_create<bitree, char>(rt, "ex38.txt");
    postorder(rt);
    bitree_destory(rt);  
    return 0;
}
